package com.bigshen.algorithm.bStack.solution02MinStack;

/**
 * 155. Min Stack
 *
 * Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
 *
 * push(x) -- Push element x onto stack.
 * pop() -- Removes the element on top of the stack.
 * top() -- Get the top element.
 * getMin() -- Retrieve the minimum element in the stack.
 *  
 *
 * Example 1:
 *
 * Input
 * ["MinStack","push","push","push","getMin","pop","top","getMin"]
 * [[],[-2],[0],[-3],[],[],[],[]]
 *
 * Output
 * [null,null,null,null,-3,null,0,-2]
 *
 * Explanation
 * MinStack minStack = new MinStack();
 * minStack.push(-2);
 * minStack.push(0);
 * minStack.push(-3);
 * minStack.getMin(); // return -3
 * minStack.pop();
 * minStack.top();    // return 0
 * minStack.getMin(); // return -2
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/min-stack
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 *
 * 执行用时：113 ms, 在所有 Java 提交中击败了5.92%的用户
 * 内存消耗：40.3 MB, 在所有 Java 提交中击败了86.90%的用户
 */
public class MinStack {

    class Node {
        int value;
        Node prev;
        Node next;
        public Node(int value) {
            this.value = value;
        }
    }

    Node head = new Node(-1);
    Node tail = new Node(-1);

    /** initialize your data structure here. */
    public MinStack() {
        head.next = tail;
        tail.prev = head;
    }

    public void push(int x) {
        Node node = new Node(x);
        node.next = tail;
        node.prev = tail.prev;
        tail.prev = node;
        node.prev.next = node;
    }

    public void pop() {
        Node pop = tail.prev;
        tail.prev = pop.prev;
        pop.prev.next = tail;
        pop = null;
    }

    public int top() {
        return tail.prev.value;
    }

    public int getMin() {
        int min = tail.prev.value;
        Node tmp = head.next;
        while(null != tmp && tmp != tail) {
            Node next = tmp.next;
            min = (tmp.value < min) ? tmp.value : min;
            tmp = next;
        }
        return min;
    }

}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */